This reference implementation visits all reachable vertices from `s`, populating `parent` and `level` trackers.

  • The algorithm uses a visited set or array to prevent processing the same vertex multiple times, which would cause an infinite loop in graphs with cycles.
  • It systematically explores the graph level by level, guaranteeing that it finds the shortest path in terms of number of edges.
  • The key takeaway is that in an adjacency list representation, each edge is considered exactly once from each of its endpoints (twice for undirected, once for directed), leading to an efficient runtime.
CLRS-Style BFS Pseudocode
BFS(G, s):
  // Initialization: O(V)
  for v in V(G):
    visited[v] ← false
    parent[v] ← NIL
    level[v] ← ∞
  
  visited[s] ← true; level[s] ← 0
  Q ← empty queue
  ENQUEUE(Q, s)
  
  // Main Loop: Each vertex enqueued/dequeued once
  while Q not empty:
    u ← DEQUEUE(Q)
    // Inner Loop: Each edge visited at most twice (undirected)
    for each w in G[u]:
      if not visited[w]:
        visited[w] ← true
        parent[w] ← u
        level[w] ← level[u] + 1
        ENQUEUE(Q, w)

// Complexity: O(V+E) time, O(V) space